package 二叉树;

import 链表.ListNode;

import java.util.ArrayList;
import java.util.List;

public class No109有序链表转换二叉搜索树 {

    /**
     * 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
     * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
     *
     * 示例:
     * 给定的有序链表： [-10, -3, 0, 5, 9],
     * 一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
     *       0
     *      / \
     *    -3   9
     *    /   /
     *  -10  5
     */

    private List<Integer> list=new ArrayList<>();

    public TreeNode sortedListToBST(ListNode head) {

        if(head==null){
            return null;
        }

        while (head!=null){
            list.add(head.val);
            head=head.next;
        }
        int mid=list.size()/2;
        TreeNode root=new TreeNode(list.get(mid));
        root.left= createNode(0,mid-1);
        root.right= createNode(mid+1,list.size()-1);
        return root;
    }

    private TreeNode createNode(int left, int right){
        if(left>right){
            return null;
        }
        int mid=(left+right)/2;
        TreeNode node=new TreeNode(list.get(mid));
        node.left=createNode(left,mid-1);
        node.right=createNode(mid+1,right);
        return node;
    }

    public static void main(String[] args) {
        No109有序链表转换二叉搜索树 n=new No109有序链表转换二叉搜索树();
        ListNode listNode = ListNode.createListNode(new int[]{-10, -3, 0, 5, 9});
        TreeNode treeNode = n.sortedListToBST(listNode);
        treeNode.printNode();
    }

}
